#pragma once

#include <string>
#include <limits>
#include <cmath>
#include <algorithm>

struct point
{
    explicit point( const std::string & s )
        : x( s.at( 0 ) - 'a' )
        , y( s.at( 1 ) - '1' ) {}
    constexpr point( int a, int b )
        : x( b )
        , y( a ) {}
    constexpr bool operator==( const point & other ) const {
        return x == other.x && y == other.y;
    }
    constexpr bool belongs( const point & min, const point & max ) const {
        return x >= min.x && x <= max.x && y >= min.y && y <= max.y;
    }
    static double length( const point & p1, const point & p2 ) {
        return std::sqrt( std::pow( ( p2.x - p1.x ), 2 ) + std::pow( ( p2.y - p1.y ), 2 ) );
    }
    const int x;
    const int y;
};

constexpr point minPoint{ 0, 0 }, maxPoint{ 7, 7 };
constexpr std::array<point, 8> knightMoves{ { { -1, -2 }, { 1, 2 }, { -2, 1 }, { -1, 2 }, { 2, -1 }, { 1, -2 }, { 2, 1 }, { -2, -1 } } };

template <class M, class P>
int find( int step, int max, const point & start, const point & finish, P && path, const M & moves ) {
    if ( finish == start || step >= max )
    { return step; }

    for ( const auto & m : moves )
    {
        point next{ start.y + m.y, start.x + m.x };
        if ( next.belongs( minPoint, maxPoint ) && std::find( path.begin(), path.end(), next ) == path.end()
             && ( point::length( start, finish ) <= 2 || point::length( next, finish ) < point::length( start, finish ) ) )
        {
            path.push_back( next );
            max = find( step + 1, max, next, finish, path, moves );
            path.pop_back();
        }
    }
    return max != std::numeric_limits<decltype( max )>::max() ? max : step;
}

int knight( std::string start, std::string finish ) {
    if( finish == "a1" || finish == "a8" || finish == "h1" || finish == "h8" ){
        return find( 0, std::numeric_limits<int>::max(), point( finish ), point( start ), std::vector<point>{}, knightMoves );
    } else {
        return find( 0, std::numeric_limits<int>::max(), point( start ), point( finish ), std::vector<point>{}, knightMoves );
    }
}
